SRM 246, Склеивание (Conglutination)

Дивизион 2, Уровень 1

Задана строка conglutination, состоящая из цифр, и целое число expectation. Можно ли строку разбить на два числа A и B так, чтобы A + B = expectation?

Класс: Conglutination

Метод: String split(String conglutination, int expectation)

Ограничения: conglutination содержит от 2 до 20 цифр, первая цифра не 0, 1 £ expectation £ 1000000000.

Вход. Строка цифр conglutination и ожидаемое значение суммы expectation.

Выход. Если строку conglutination невозможно разбить на части, сумма чисел в которых равна expectation, то вывести пустую строку. Иначе вывести строку в виде “A+B”.

Пример входа

conglutination	expectation
“22”	4
“536”	41
“123456000789”	1235349
“123456789”	4245

Пример выхода

“2+2”

“5+36”

“1234560+00789”

“”

РЕШЕНИЕ

обработка строк

Задача решается полным перебором вариантов разбиения строки на две части. Если размер входной строки равен len = conglutination.size(), то следует перебрать len – 1 разбиений: левая часть строки содержит i цифр, правая len – i цифр, 1 £ i £ len – 1.

Если a – переменная типа string, то a.substr(pos, l) является подстрокой, начинающейся с позиции pos и имеющей длину l. Если второй аргумент отсутствует, то выделяется подстрока с позиции pos до коца строки.

Функция a.c_str() преобразовывает строку a в массив символов, с которым работают функции ввода-вывода библиотеки <stdio.h>. Чтение форматированных данных из строки совершается функцией sscanf.

Требуемое разбиение строки на два числа не будет найдено, если по окончанию цикла переменная i будет содержать значение len.

ПРОГРАММА

#include <cstdio>

#include <string>

using namespace std;

class Conglutination

{

public:

string split(string conglutination, int expectation)

{

string a, b, res = "";

int i, x, y;

for(i = 1; i < conglutination.size(); i++)

{

a = conglutination.substr(0,i);

b = conglutination.substr(i);

sscanf(a.c_str(),"%d",&x);

sscanf(b.c_str(),"%d",&y);

if (x + y == expectation) break;

}

if (i < conglutination.size()) res = a + '+' + b;

return res;

}

};